class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
vector<int>dp(amount+1,-1);//初始化数组
int i,j;
dp[0]=0;
for(i=0;i<=amount;i++)//遍历整个金额数组，找出其最优解
{
    for(j=0;j<coins.size();j++)//遍历面值数组，找到其最优解
    {
    if(coins[j]<=i&&dp[i-coins[j]]!=-1){//找出小于金额的面值，如果有最优解
        if(dp[i]==-1 || dp[i]>dp[i-coins[j]]+1)//如果此金额没有最优解，或者最优解比正在计算的最优
        {
            dp[i]=dp[i-coins[j]]+1;
        }
    }

}

}
return dp[amount];
    }
};